package com.lw.leetcode.greedy.c;

import org.omg.CORBA.INTERNAL;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 *857. 雇佣 K 名工人的最低成本
 * @author liw
 * @version 1.0
 * @date 2023/1/9 16:10
 */
public class MincostToHireWorkers {

    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int length = quality.length;
        int[][] arr = new int[length][2];
        for (int i = 0; i < length; i++) {
            int[] items = arr[i];
            items[0] = quality[i];
            items[1] = wage[i];
        }
        Arrays.sort(arr, (a, b) -> Double.compare((double) a[1]/ a[0], (double) b[1]/b[0]));
        int sum = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        for (int i = 0; i < k; i++) {
            sum += arr[i][0];
            queue.add(arr[i][0]);
        }
        double value = sum *  ((double)arr[k - 1][1]/arr[k - 1][0]);
        for (int i = k; i < length; i++) {
            int a = arr[i][0];
            int b = arr[i][1];
            queue.add(a);
            sum += a;
            sum -= queue.poll();
            value = Math.min(value, sum * ((double)b/a));
        }
        return value;
    }

}
